//
// Created by 许欣鑫 on 25-3-25.
//

#ifndef SOLUTION_H
#define SOLUTION_H
#include <numeric>
#include <vector>
using namespace std;

class Solution {
public:
    //爬楼梯 https://leetcode.cn/problems/climbing-stairs/
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    //使用最小花费爬楼梯 https://leetcode.cn/problems/min-cost-climbing-stairs/description/
    int minCostClimbingStairs(vector<int> &cost) {
        int n = cost.size();
        vector<int> dp(n, 0);
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);
        }
        return min(dp[n - 1], dp[n - 2]);
    }

    //组合总和 Ⅳ https://leetcode.cn/problems/combination-sum-iv/description/
    //nums数组相当于每次可以走的步数 target相当于楼层高度
    int combinationSum4(vector<int> &nums, int target) {
        std::vector<unsigned long long> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num: nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }

    //统计构造好字符串的方案数 https://leetcode.cn/problems/count-ways-to-build-good-strings/description/
    //low-high 指的是字符串的长度范围 zero和one指的是一次添加0和1的个数
    //算两次 dp以high来计算
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<long long> dp(high + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= high; i++) {
            if (i >= zero) {
                dp[i] += dp[i - zero] % 1000000007;
            }
            if (i >= one) {
                dp[i] += dp[i - one] % 1000000007;
            }
        }
        auto ans = accumulate(dp.begin() + low, dp.begin() + high + 1, 0LL, [](long long a, long long b) {
            return (a + b) % 1000000007;
        });
        return static_cast<int>(ans);
    }

    //统计打字方案数 https://leetcode.cn/problems/count-number-of-texts/description/
    //生成连续索引 然后每个数字单独计算(使用dp数组,只计算一次最大的) 最后乘起来
    const int MOD = 1000000007;

    vector<long long> computeDP(int k, int maxCount) {
        vector<long long> dp(maxCount + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= maxCount; i++) {
            for (int j = 1; j <= k && i - j >= 0; j++) {
                dp[i] = (dp[i] + dp[i - j]) % MOD;
            }
        }
        return dp;
    }

    int countTexts(string pressedKeys) {
        int n = pressedKeys.size();
        int maxCount = 0;
        for (int i = 0; i < n; ) {
            char digit = pressedKeys[i];
            int count = 0;
            while (i < n && pressedKeys[i] == digit) {
                count++;
                i++;
            }
            maxCount = max(maxCount, count);
        }

        vector<long long> dp3 = computeDP(3, maxCount); // '2', '3', '4', '5', '6', '8'
        vector<long long> dp4 = computeDP(4, maxCount); // '7', '9'

        long long result = 1;
        for (int i = 0; i < n; ) {
            char digit = pressedKeys[i];
            int count = 0;
            while (i < n && pressedKeys[i] == digit) {
                count++;
                i++;
            }
            if (digit == '7' || digit == '9') {
                result = (result * dp4[count]) % MOD;
            } else {
                result = (result * dp3[count]) % MOD;
            }
        }
        return static_cast<int>(result);
    }
};
#endif //SOLUTION_H
